#pragma once
#include "../LinkList.h"
#include "../LevelListNode.h"

#define BASSERTS //
#define BLOGINFO //

namespace qb{
	namespace base{
		namespace container{
			template<typename Entry, typename Key, typename Comparator>
			class OrderedRootNode
			{
			public:
				typedef LevelNode<Entry, OrderedRootNode> NodeType;
				typedef DoubleLinkList<Entry> EntryQueue;
				typedef CachedObjectPool<NodeType> NodePool;
				typedef OrderedRootNode*	RootPtr;
				typedef NodeType*		 NodePtr;
				typedef Entry*			 EntryPtr;
				typedef Key			 KeyType;
			protected:
				class NodeCursor{
				public:
					NodePtr	node;
					RootPtr	root;
					int		index;
					NodeCursor(RootPtr r, NodePtr n, int i) :root(r), node(n), index(i){}
					inline void ToRight(int step)
					{
						index += step;
						for (int i = 0; i < step; i++){ node = node->GetNext(); }
					}
					int  CompareWith(const KeyType& k, Comparator* comp)
					{
						if ((*comp)(node->GetFirstEntry()->key, k)>0)
							return 1;
						if ((*comp)(root->GetLastEntry(node)->key, k) < 0)
							return -1;
						return 0;
					}
				};
				class EntryCursor{
				public:
					Entry*	node;
					RootPtr	root;
					int		index;
					EntryCursor(RootPtr r, Entry* et, int i) :root(r), node(et), index(i){}
					inline void ToRight(int step)
					{
						index += step;
						for (int i = 0; i < step; i++){ node = node->GetNext(); }
					}
					inline int  CompareWith(const KeyType& k, Comparator* comp)
					{
						return (*comp)(node->key, k);
					}
				};
				int			m_except_count;		// 
				int			m_find_node_step;	// 
				int			m_max_count;		// 测试等同于m_except_count时性能更好
				NodePool	m_node_pool;		// 
				NodePtr		m_find_cache;		//
				NodeType	m_root;				//
				EntryPtr	m_tail;				// 指向最末位的指针,用于加速GetLastEntry
				int			m_cmp_node, m_cmp_cache, m_cmp_entry;
			public:
				OrderedRootNode(int expectCount) :m_except_count(expectCount), m_max_count((int)(expectCount * 1)),
					m_find_cache(nullptr), m_find_node_step(2), m_tail(nullptr),
					m_cmp_node(0), m_cmp_cache(0), m_cmp_entry(0)
				{}
				~OrderedRootNode(){ destroy(); }
				void SwapRoot(NodeType* root, Entry* tail)
				{
					m_root.Swap(root);
					m_tail = tail;
				}
				void set_expect(int nexpect){ m_except_count = nexpect; m_max_count = nexpect * 1; }
				int get_expect()const{ return m_except_count; }
				void set_max(int nmax){ m_max_count = nmax < m_except_count ? m_except_count : nmax; }
				void reserve_pool(int nsize){ m_node_pool.Reserve(nsize); }
				void destroy(){
					m_root.destroy(this);
					m_tail = nullptr;
					m_find_cache = nullptr;
				}
				Entry* GetLastEntry(NodePtr node)
				{//返回节点node的最末位的一个Entry指针,其中m_tail是根节点的最末位Entry指针
					DEBUG_ASSERT(node && (node == &m_root || node->GetRoot() == &m_root));
					while (node)
					{
						if (node->GetNext())
							return node->GetNext()->GetFirstEntry()->GetPrev();
						node = node->GetParent();
					}
					return m_tail;
				}
				Entry* GetFirstEntry()const{return m_root.GetFirstEntry();}
			protected:
				bool is_parent_of(NodePtr node, Entry* e)const
				{
					NodePtr p = (e&&node) ? e->GetNode() : nullptr;
					while (p){if (p == node)return true;p = p->GetParent();}
					return false;
				}
				bool check_insert(NodePtr node, Entry* e, Comparator* comp)
				{
					// 功能:确保e要插入到节点node中,作为node新的子节点
					DEBUG_ASSERT(node && e && comp);
					Entry* first = node->GetFirstEntry();
					Entry* last = GetLastEntry(node);
					DEBUG_ASSERT(first && last && is_parent_of(node, first) && is_parent_of(node, last));
					Entry* prev = first->GetPrev();//上一个末尾
					Entry* next = last->GetNext();//下一个开头

					// 检查node的节点两端的递增性prev<=first<=last<=next
					if (prev && (*comp)(prev->key, first->key) > 0)
						return false;
					if ((*comp)(first->key, last->key) > 0)
						return false;
					if (next && (*comp)(last->key, next->key) > 0)
						return false;
					
					// 检查插入点在node的合理性:prev<e<=last
					if (prev && (*comp)(prev->key, e->key) >= 0)
						return false;
					if ((*comp)(e->key, last->key) > 0)
						return false;
					return true;
				}
			protected:
				template<typename Type, typename Cursor>
				Type* find_type(Type* first, Type* last, int ncount, Entry* e, Comparator* comp)
				{
					DEBUG_ASSERT(last && ncount >= 1);
					Cursor left(this, first, 0);
					Cursor right(this, last, ncount - 1);
					Cursor mid(left);
					const KeyType& k = e->key;
					int bsearch_dist = 1 << m_find_node_step;//2退化成2分法
					while (right.index - left.index > bsearch_dist)
					{
						mid = left;
						int step = (right.index - left.index) >> m_find_node_step;
						for (int i = 0; i < bsearch_dist - 1; i++, left = mid)
						{
							mid.ToRight(step);
							if (mid.CompareWith(k, comp) >= 0)
							{
								right = mid;
								break;
							}
						}
					}
					mid = left;
					for (int i = left.index; i < right.index; i++, mid.ToRight(1))
					{
						if (mid.CompareWith(k, comp) >= 0)break;
					}
					return mid.node;
				}
				inline int CompareNodeWithKey(NodeType* node, const KeyType& k, Comparator* comp)
				{
					add_cmp_count(1);
					if ((*comp)(node->GetFirstEntry()->key, k)>0)
						return 1;
					add_cmp_count(1);
					if ((*comp)(GetLastEntry(node)->key, k) < 0)
						return -1;
					return 0;
				}
				NodeType* find_node(NodeType* first, NodeType* last, int ncount, Entry* e, Comparator* comp)
				{
					// 功能    :在节点[first,last]中找到e应该插入的节点,确保插入后递增有序
					// 入口条件:first,last必须有效,且父亲有效且相同
					// 出口条件:与first属于同一层的兄弟节点
					DEBUG_ASSERT(first && last && first->GetParent() && first->GetParent() == last->GetParent());
					DEBUG_ASSERT(last && ncount >= 1 && e && comp);
					int left_index = 0, right_index = ncount - 1, mid_index = 0;
					NodeType* left = first;
					NodeType* right = last;
					NodeType* mid = left;
					const KeyType& k = e->key;
					int find_step = m_find_node_step;
					int bsearch_dist = 1 << find_step;//2退化成2分法
					while (right_index - left_index > bsearch_dist)
					{
						mid = left; mid_index = left_index;
						int step = (right_index - left_index) >> find_step;
						for (int i = 0; i < bsearch_dist - 1; ++i)
						{
							mid_index += step;
							for (int j = 0; j < step; j++)mid = mid->GetNext();
							add_cmp_count(1);
							if ((*comp)(GetLastEntry(mid)->key, k) >= 0)
							{
								right = mid; right_index = mid_index;
								break;
							}
							left = mid; left_index = mid_index;
						}
					}
					mid = left; mid_index = left_index;
					for (int i = left_index; i < right_index; ++i, ++mid_index, mid = mid->GetNext())
					{
						add_cmp_count(1);
						if ((*comp)(GetLastEntry(mid)->key, k) >= 0)
							break;
					}
					DEBUG_ASSERT(mid && mid->GetParent() == first->GetParent());
					DEBUG_ASSERT(check_insert(mid, e, comp));
					return mid;
				}

				Entry* find_entry(Entry* first, Entry* last, int ncount, Entry* e, Comparator* comp)
				{
					// first < e <= last
					DEBUG_ASSERT(first && last && ncount >= 1);
					DEBUG_ASSERT(first->GetNode() == last->GetNode());
					DEBUG_ASSERT((*comp)(first->key, e->key) < 0);
					DEBUG_ASSERT((*comp)(e->key, last->key) <= 0);
					int left_index = 0, right_index = ncount - 1, mid_index = 0;
					Entry* left = first;
					Entry* right = last;
					Entry* mid = left;
					const KeyType& k = e->key;
					int find_step = m_find_node_step;
					int bsearch_dist = 1 << find_step;//2退化成2分法
					while (right_index - left_index > bsearch_dist)
					{
						mid = left; mid_index = left_index;
						int step = (right_index - left_index) >> find_step;
						for (int i = 0; i < bsearch_dist - 1; ++i)
						{
							mid_index += step;
							for (int j = 0; j < step; j++)mid = mid->GetNext();
							add_cmp_count(2);
							if ((*comp)(mid->key, k) >= 0)
							{
								right = mid; right_index = mid_index;
								break;
							}
							left_index = mid_index; left = mid;
						}
					}
					mid = left; mid_index = left_index;
					for (int i = left_index; i < right_index; ++i, ++mid_index, mid = mid->GetNext())
					{
						add_cmp_count(2);
						if ((*comp)(mid->key, k) >= 0)break;
					}

					// 检查
					DEBUG_ASSERT(mid != nullptr && mid->GetNode() == last->GetNode());
					Entry* prev = mid->GetPrev();
					if (prev){
						DEBUG_ASSERT((*comp)(prev->key, e->key) < 0);
					}
					DEBUG_ASSERT((*comp)(e->key, mid->key) <= 0);
					DEBUG_ASSERT((*comp)(first->key, mid->key) < 0);
					DEBUG_ASSERT((*comp)(mid->key, last->key) <= 0);
					return mid;
				}

				NodePtr find_node_from_cache(Entry* e, Comparator* comp, Entry* hint)
				{
					//借用上次搜索的节点,假设两次搜索很可能位于相同位置
					if (m_find_cache == nullptr)
						return &m_root;
					NodePtr root = &m_root;
					int nstart = 0;
					NodePtr starts[2] = { nullptr, nullptr };
					if (m_find_cache)starts[nstart++] = m_find_cache;
					if (hint && hint->GetNode() != m_find_cache)starts[nstart++] = hint->GetNode();
					const KeyType& k = e->key;
					for (int i = 0; i < nstart; i++)
					{
						NodePtr node = starts[i];
						while (node != root)
						{
							add_cmp_count(0);
							Entry* first = node->GetFirstEntry();
							int cmpfirst = (*comp)(k, first->key);
							if (cmpfirst > 0)
							{
								add_cmp_count(0);
								Entry* last = GetLastEntry(node);
								int cmplast = (*comp)(k, last->key);
								if (cmplast < 0)
									return node;
								if (cmplast == 0 && last->GetNext() == nullptr)
									return node;
							}
							else if (cmpfirst == 0 && first->GetPrev() == nullptr)
								return node;
							node = node->GetParent();
						}
					}
					return root;
				}
				inline void reset_cmp_count(){ m_cmp_cache = m_cmp_entry = m_cmp_node = 0; }
				inline void add_cmp_count(int type){
					switch (type)
					{
					case 0:m_cmp_cache++; break;
					case 1:m_cmp_node++; break;
					case 2:m_cmp_entry++; break;
					}
				}
				Entry* find_insert(Entry* e, Comparator* comp, Entry* hint = nullptr)
				{
					// 功能:找到e该插入的位置,确保此位置之前都比e小(<),此位置及之后都不比e小(>=)
					//      如果应该插入到最末位,返回空
					//		hint是推荐参考位置,即调用方确信很可能应该插入到该位置附近
					CHECK_SINGLE(e);
					// hint是e的上一次位置,假设e的值变化不大,那么e很可能还在hint所在的node附近
					// 经过随机数据测试,有比较明显的性能提升(2.0,2.2)==>(2.4,2.8)
					
					// 检查总体个数,以及首尾位置
					if (m_root.size() <= 0)
						return nullptr;
					reset_cmp_count();
					EntryPtr rootfirst = m_root.GetFirstEntry();
					if (rootfirst && (*comp)(e->key, rootfirst->key) <= 0)
					{
						m_find_cache = rootfirst->GetNode();
						return rootfirst;
					}
					if (m_tail && (*comp)(e->key, m_tail->key) > 0)
						return nullptr;

					// 逐层定位到应该插入的最下面的那个节点
					NodePtr node = find_node_from_cache(e, comp, hint);
					while (node->GetFirstChild() != nullptr)
					{
						DEBUG_ASSERT(node->GetLastChild() != nullptr);
						node = find_node(node->GetFirstChild(),node->GetLastChild(), node->GetChildCount(), e, comp);
					}

					// 现在已经确定要插入的节点就是node,node必须是叶子节点
					DEBUG_ASSERT(node->IsLeaf());
					m_find_cache = node;
					Entry* first = node->GetFirstEntry();
					if (first == nullptr){
						DEBUG_ASSERT(m_root.size() <= 0);
						return nullptr;
					}

					// 之所以要提前检测第一个,是因为GetLastEntry有开销
					// 有待优化:GetLastEntry可以想办法消除
					if ((*comp)(e->key, first->key) <= 0)
						return first;
					Entry* last = GetLastEntry(node);
					DEBUG_ASSERT(last && last->GetNode() == node && (*comp)(e->key,last->key)<=0);

					Entry* pos = find_entry(first, last, node->size(), e, comp);
					DEBUG_ASSERT(pos && pos->GetNode() == first->GetNode() && pos->GetNode() == node);
					DEBUG_ASSERT(check_pos(e, comp, pos));
					return pos;
				}
				bool is_child_of(Entry* et, NodeType* node)const{
					NodeType* parent = et->GetNode();
					while (parent)
					{
						if (parent == node)return true;
						parent = parent->GetParent();
					}
					return false;
				}
			public:
				bool check_node_sorted(NodeType* node, Comparator* comp,bool recursive=true)
				{
					if (node == nullptr)
						return true;
					DEBUG_ASSERT_FALSE(comp);
					Entry* first = node->GetFirstEntry();
					Entry* last = GetLastEntry(node);
					DEBUG_ASSERT_FALSE(is_child_of(first, node));
					DEBUG_ASSERT_FALSE(is_child_of(last, node));

					if (first == nullptr){
						DEBUG_ASSERT_FALSE(node->size() == 0 && node->GetChildCount() == 0);
						return true;
					}
					Entry* prev = first->GetPrev();//上一个末尾
					Entry* next = last->GetNext();//下一个开头
					if (prev){
						DEBUG_ASSERT_FALSE(!is_child_of(prev, node));
						DEBUG_ASSERT_FALSE((*comp)(prev->key, first->key) <= 0);
					}
					if (next){
						DEBUG_ASSERT_FALSE(!is_child_of(next, node));
						DEBUG_ASSERT_FALSE(last && (*comp)(last->key, next->key) <= 0);
					}
					if (node->GetParent() && recursive)
					{
						DEBUG_ASSERT_FALSE(node->GetParent() != node);
						DEBUG_ASSERT_FALSE(check_node_sorted(node->GetParent(), comp, recursive));
					}
					return true;
				}
				bool check_pos(Entry* e, Comparator* comp,Entry* pos)const
				{
					if (pos == nullptr || pos==e)
						return false;
					int cmp = (*comp)(e->key, pos->key);
					if (cmp > 0)
						return false;
					Entry* prev = pos->GetPrev();
					if (prev)
					{
						cmp = (*comp)(prev->key, e->key);
						if (cmp >= 0)
						{
							cmp = (*comp)(prev->key, e->key);
							BASSERTS(0, "");
							cmp = (*comp)(prev->key, e->key);
							return false;
						}
					}
					return true;
				}
				NodeType* Alloc(){ NodeType* node = m_node_pool.Alloc(); node->reset(); return node; }
				void Free(NodeType* node){
					if (m_find_cache == node)m_find_cache = nullptr;
					m_node_pool.Free(node);
				}
				int size()const{ return m_root.size(); }
				bool erase(Entry* e, Comparator* comp, bool check=true)
				{
					// 入口条件:e必须有效,必须在当前节点中
					DEBUG_ASSERT(check_entry_in_tree(e));
					int last_size = m_root.size();
					NodePtr node = e->GetNode();
					EntryPtr prev = e->GetPrev();
					//DEBUG_ASSERT(check_node_sorted(node, comp));
					m_root.erase_impl(node, e, this);
					DEBUG_ASSERT(!check || check_node_sorted(node, comp));
					NodePtr bnode = m_root.balance(node, this, m_except_count, m_max_count);
					DEBUG_ASSERT(!check || (bnode && check_node_sorted(node, comp)));
					if (e == m_tail)
					{
						m_tail = prev;
					}
					DEBUG_ASSERT(check_entry_solitary(e));
					DEBUG_ASSERT(last_size = m_root.size() + 1);
					return true;
				}
				bool insert(Entry* e, Comparator* comp, Entry* hint = nullptr)
				{
					// 入口条件:e必须不在任何单链表中,必须有效
					DEBUG_ASSERT(check_entry_solitary(e));
					int last_size = m_root.size();
					Entry* cur = find_insert(e, comp, hint);
					if (cur)
					{
						NodePtr node = cur->GetNode();
						DEBUG_ASSERT(check_node_sorted(node, comp));
						m_root.insert_impl(e, cur, node, this);
						DEBUG_ASSERT(last_size + 1 == m_root.size());
						DEBUG_ASSERT(check_node_sorted(node, comp));
						NodePtr bnode= m_root.balance(node, this, m_except_count, m_max_count);
						DEBUG_ASSERT(check_node_sorted(bnode, comp));
					}
					else
					{
						// 不用append,是因为里面更宽松,要求last<=e,而这里插入时要求更
						// 严格,要求last<e,e是第一个比last大的
						Entry* last = at(size() - 1);
						if (last){ DEBUG_ASSERT(last->GetNext() == nullptr && (*comp)(last->key, e->key) < 0); }
						NodePtr node = m_root.append_impl(e, last);
						m_tail = e;
						m_find_cache = m_tail->GetNode();
						DEBUG_ASSERT(last_size + 1 == m_root.size());
						NodePtr bnode = m_root.balance(node, this, m_except_count, m_max_count);
						DEBUG_ASSERT(e->GetNext() == nullptr && e->GetPrev() == last);
						DEBUG_ASSERT(check_node_sorted(bnode, comp));
					}
					//出口条件:e必须属于一个节点,节点必须属于当前根节点;插入必须成功
					DEBUG_ASSERT(check_entry_in_tree(e));
					DEBUG_ASSERT(last_size + 1 == m_root.size());
					return true;
				}
				void append(Entry* e, Comparator* comp)
				{
					// 已经不通过此接口更新,因为速度较慢,通过NodeBuilder直接构造
					Entry* last = at(size() - 1);
					if (last){ DEBUG_ASSERT(last->GetNext() == nullptr && (*comp)(last->key, e->key) <= 0); }
					NodePtr node = m_root.append_impl(e, last);
					m_tail = e;
					m_root.balance(node, this, m_except_count, m_max_count);
				}
				int find(Entry* et)const
				{
					// 预计level*m_step_count 次遍历累加
					NodePtr node = et ? et->GetNode() : nullptr;
					if (node && node->GetRoot() == &m_root)
					{
						int offset = DoubleLinkList<Entry>::Find(node->GetFirstEntry(), node->size(), et);
						DEBUG_ASSERT(offset >= 0);
						offset += node->GetRootOffset();
						return offset;
					}
					return -1;
				}
				Entry* at(int index)
				{
					const NodeType* node = nullptr;
					if (index < 0 || index >= size())return nullptr;
					if (index == size() - 1 && m_tail)return m_tail;
					return m_root.at_impl(index, node);
				}
				const Entry* at(int index)const
				{
					const NodeType* node = nullptr;
					if (index < 0 || index >= size())return nullptr;
					if (index == size() - 1 && m_tail)return m_tail;
					return m_root.at_impl(index, node);
				}
			public:
				bool check(bool recursive)const{ return recursive ? m_root.check_all() : m_root.check(); }

				bool check_entry_in_tree(Entry* e)const
				{
					if (e == nullptr)return false;
					if (e->GetNode() == nullptr)return false;
					if (e->GetNode()->GetRoot() != &m_root)return false;
					return true;
				}
				bool check_entry_solitary(Entry* e)const
				{
					if (e == nullptr)return false;
					if (e->GetNext() || e->GetPrev())return false;
					if (e->GetNode())return false;
					return true;
				}
				void dump()const{
					int nnode = m_root.GetNodeCount(true) + 1;
					int npool = m_node_pool.GetCount();
					BLOGINFO("NodeTree:%8d NodePool:%8d NodeAll:%8d bytes:%8d", nnode, npool, nnode + npool, (nnode + npool)*sizeof(NodeType));
					m_root.dump(0);
				}
			};
		}
	}//namespace base;
}//namespace ss;
